#include <iostream>
#include <cstdio>
#include <random>
#include <ctime>
using namespace std;
default_random_engine e;
void init(){
    e.seed(time(0));
}
long long randint(long long min,long long max){ //随机min到max之间的整数
    uniform_int_distribution<long long> u(min,max); // 左闭右闭区间
    return u(e);
}
double randouble(double min,double max){ // 随机min到max之间的小数
    return randint(min * 1e8,max * 1e8) / 1e8;
}

long long qpow(long long a, long long b) {
	long long ans = 1;
	for (; b; b >>= 1) {
		if (b & 1) ans = (long long)ans * a;
		a = (long long)a * a;
	}
	return ans;
}